We present a learning-based approach to computing solutions for certain NP-hard problems. Our approach combines deep learning techniques with useful algorithmic elements from classic heuristics. The central component is a graph convolutional network that is trained to estimate the likelihood, for each vertex in a graph, of whether this vertex is part of the optimal solution. The network is designed and trained to synthesize a diverse set of solutions, which enables rapid exploration of the solution space via tree search. The presented approach is evaluated on four canonical NP-hard problems and five datasets, which include benchmark satisfiability problems and real social network graphs with up to a hundred thousand nodes. Experimental results demonstrate that the presented approach substantially outperforms recent deep learning work, and performs on par with highly optimized state-of-the-art heuristic solvers for some NP-hard problems. Experiments indicate that our approach generalizes across datasets, and scales to graphs that are orders of magnitude larger than those used during training.

This paper proposes a method combining graph neural networks and guided tree search to tackle combinatorial optimization problems. The authors focus on the Maximum Independent Set (MIS), the Minimum Vertex Cover (MVC), Maximal Clique (MC) and Satisfiability which are all reduced to MIS. Given a MIS instance represented by a graph, the method consists in using the predictions of a graph convolutional neural (GCN) network, which is trained with binary cross-entropy to predict whether a vertex is in the maximum independent set, as input for a greedy search algorithm. The greedy search algorithm considers vertices in descending order of the GCN outputs, adding them to the independent set if doing so doesn't violate the independence assumption. Once this isn't possible, the process is repeated on the residual graph until termination. The method is further augmented with diversity, allowing the GCN to output different probability maps, and a tree search (partial solutions are added to a queue from which they will be randomly sampled to be further constructed).

We present a learning-based approach to computing solutions for certain NP-hard problems. Our approach combines deep learning techniques with useful algorithmic elements from classic heuristics. The central component is a graph convolutional network that is trained to estimate the likelihood, for each vertex in a graph, of whether this vertex is part of the optimal solution. The network is designed and trained to synthesize a diverse set of solutions, which enables rapid exploration of the solution space via tree search. The presented approach is evaluated on four canonical NP-hard problems and five datasets, which include benchmark satisfiability problems and real social network graphs with up to a hundred thousand nodes.